package com.ayuer.chapter10;

import java.util.*;

public class Dijkstra {

    public static void main(String[] args) {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");
        v1.edges = List.of(new Edge(v3, 9), new Edge(v2, 7), new Edge(v6, 14));
        v2.edges = List.of(new Edge(v4, 15));
        v3.edges = List.of(new Edge(v4, 11), new Edge(v6, 2));
        v4.edges = List.of(new Edge(v5, 6));
        v5.edges = List.of();
        v6.edges = List.of(new Edge(v5, 9));

        List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6);

        //无法处理负权重
        dijkstra(graph, v1);
        //可以处理负权重
        bellmanFord(graph, v1);


    }

    private static void bellmanFord(List<Vertex> graph, Vertex source) {

        source.distance = 0;
        int size = graph.size() - 1;
        // n - 1 轮
        for (int i = 0; i < size; i++) {
            // 获取所有顶点
            for (int i1 = 0; i1 < graph.size(); i1++) {
                Vertex v = graph.get(i1);
                // 对每个顶点的边进行遍历
                for (int j = 0; j < v.edges.size(); j++) {
                    // 如果距离小于linked就进行更新
                    int currentDistance = v.distance + v.edges.get(j).weight;
                    int targetDistance = v.edges.get(j).linked.distance;
                    if (currentDistance < targetDistance) {
                        v.edges.get(j).linked.distance = v.distance + v.edges.get(j).weight;
                    }
                }
            }
        }

        System.out.println(graph);
    }

    public static void dijkstra(List<Vertex> vertices, Vertex source) {
        source.distance = 0;
        PriorityQueue<Vertex> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.distance));
        queue.addAll(vertices);
        while (!queue.isEmpty()) {
            //选取当前顶点
            Vertex current = queue.peek();
            //更新当前顶点邻居距离
            for (Edge edge : current.edges) {
                Vertex linked = edge.linked;
                if (!linked.visited) {
                    int currDist = current.distance + edge.weight;
                    if (currDist < linked.distance) {
                        //小于的话就更新
                        linked.distance = currDist;
                        //重新加入队列
                        queue.offer(linked);
                    }
                }
            }
            queue.poll();
            current.visited = true;
        }

        System.out.println(vertices);

    }
}


